package com.hackerrank.challenges.quicksort;

// Head ends here
import java.util.*;
public class Solution {

	static void quickSort(int[] ar) {
		if(ar.length <= 1)
			return;
		int p = ar[0];
		List<Integer> fh = new ArrayList<Integer>(), sh = new ArrayList<Integer>();
		for(int i = 1; i < ar.length; i++) {
			if(ar[i] <= p)
				fh.add(ar[i]);
			else
				sh.add(ar[i]);
		}
		int[] ar1 = new int[fh.size()];
		for(int i = 0; i < fh.size(); i++)
			ar1[i] = fh.get(i);
		quickSort(ar1);
		for(int i = 0; i < ar1.length; i++)
			ar[i] = ar1[i];
		ar[ar1.length] = p;
		int[] ar2 = new int[sh.size()];
		for(int i = 0; i < sh.size(); i++)
			ar2[i] = sh.get(i);
		quickSort(ar2);
		for(int i = 0; i < ar2.length; i++)
			ar[i + ar1.length + 1] = ar2[i];
		printArray(ar);
	}

	// Tail starts here
	static void printArray(int[] ar) {
		for(int n: ar)
			System.out.print(n + " ");
		System.out.println("");
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] ar = new int[n];
		for(int i=0;i<n;i++)
			ar[i]=in.nextInt(); 
		quickSort(ar);
	}    
}
